package cn.summit.sort;

import java.util.Arrays;

/**
 * 希尔排序- 基于插入排序
 *
 * @author summit
 * @since 2021/8/16 17:07
 */
public class ShellSortTest {
	public static void main(String[] args) {
		int[] arr = { 11, 10, 6, 2, 1, 5, 2, 3 };
		shellSort(arr);

		System.out.println(Arrays.toString(arr));
	}

	private static int[] shellSort(int[] arr) {
		int h = 1;
		while (h < arr.length / 3) {
			h = h * 3 + 1;
		}
		for (int gap = h; gap > 0; gap = (gap - 1) / 3) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i; j > gap - 1; j -= gap) {
					if (arr[j] < arr[j - gap]) {
						swap(arr, j, j - gap);
					}
				}
			}
		}


		return arr;
	}

	public static void swap(int[] arr, int a, int b) {
		int tmp = arr[a];
		arr[a] = arr[b];
		arr[b] = tmp;
	}

}
